/*
 * @Author: your name
 * @Date: 2020-04-12 22:20:54
 * @LastEditTime: 2020-04-12 23:53:14
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \leetcode-exercise\491-递增子序列\answer.c
 */

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int g_index;
int g_size;g_size;
int **g_ret = NULL;
int *g_retCol = NULL;

void DFS(int * nums, int numsSize, int index, int *arr, int arrSize)
{
    int i;
    /* DFS 边界处理，搜索达到边界，或则选到非递增的数据 */
    if((index == numsSize) || (arr[arrSize - 1] > nums[index]))
    {
        /* 判断当前结果是否可以加入其中 */
        if(arrSize >= 2) {
            g_ret[g_index] = (int *)malloc(sizeof(int)* numsSize); 
            g_retCol[g_index] = arrSize;
            for (i = 0; i < arrSize; i++){
                g_ret[g_index][i] = arr[i];
            } 
            g_index++;
        }
        return;
    }
    /* 判断是否将该数值插入到arr数组中 */
    /* 选择不插入 */
    DFS(nums, numsSize, index+1 , arr, arrSize);
    /* 选择插入 */
    arr[arrSize] = nums[index];
    DFS(nums, numsSize, index+1, arr, arrSize+1);

}

int compare(const void *a, const void *b)
{
    int i;
    for(i = 0 ; i < g_size; i++){
        if (*((int *)a+i) < *((int *)b+i))
        {
            return -1;
        } else if (*((int *)a+i) < *((int *)b+i))
        {
            return 1;
        }
    }
    return 0;
}

int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int i;
    int *arr = (int *)malloc(sizeof(int)*numsSize);
    if(numsSize < 2) {
        *returnSize = 0;
        return NULL;
    }
    g_ret = (int **)malloc(sizeof(int *) * numsSize * numsSize);
    g_retCol = (int *)malloc(sizeof(int *)* numsSize*numsSize); 
    g_size = numsSize;
    g_index = 0; 
    /* 依次取各个点作为起点进行遍历 */
    for (i = 0 ; i < numsSize - 1; i++) {
        arr[0] = nums[i];
        DFS(nums, numsSize, i+1, arr, 1);
    }
    /* 结果排序后 去重 */
    qsort(g_ret, g_index, sizeof(int)*numsSize, &compare);
     
    *returnSize = g_index;
    *returnColumnSizes = g_retCol;
    return g_ret;
}